from collections import deque

GRAPH = {
    'A': ['B', 'F'],
    'B': ['C', 'I', 'G'],
    'C': ['B', 'I', 'D'],
    'D': ['C', 'I', 'G', 'H', 'E'],
    'E': ['D', 'H', 'F'],
    'F': ['A', 'G', 'E'],
    'G': ['B', 'F', 'H', 'D'],
    'H': ['G', 'D', 'E'],
    'I': ['B', 'C', 'D'],
}


class Queue:
    def __init__(self):
        self._deque = deque()

    def push(self, value):
        return self._deque.append(value)

    def pop(self):
        return self._deque.popleft()

    def __len__(self):
        return len(self._deque)


# 广度算法
def bfs(graph, start):
    seach_queue = Queue()
    seach_queue.push(start)
    seached = set()
    while seach_queue:  # 队列不为空就继续
        cur_node = seach_queue.pop()
        if cur_node not in seached:
            print(cur_node)
            seached.add(cur_node)
            for node in graph[cur_node]:  # 被搜索过的将邻居节点入队
                seach_queue.push(node)


DFS_SEARCHD = set()


# 递归深度算法
def dfs(graph, start):
    if start not in DFS_SEARCHD:
        print(start)
        DFS_SEARCHD.add(start)
    for node in graph[start]:
        if node not in DFS_SEARCHD:
            dfs(graph, node)


# 栈
class Stack(object):
    def __init__(self):
        self._deque = deque()

    def push(self, value):
        return self._deque.append(value)

    def pop(self):
        return self._deque.pop()

    def __len__(self):
        return len(self._deque)


def dfs1(graph, start):
    stack = Stack()
    stack.push(start)
    searched = set()
    while stack:
        cur_node = stack.pop()
        if cur_node not in searched:
            print(cur_node)
            searched.add(cur_node)
            for node in reversed(graph[cur_node]):
                stack.push(node)


def bfs1(graph, start):
    seach_queue = Queue()
    seach_queue.push(start)
    seached = set()
    while seach_queue:  # 队列不为空就继续
        cur_node = seach_queue.pop()
        if cur_node not in seached:
            print(cur_node)
            seached.add(cur_node)
            for node in graph[cur_node]:  # 被搜索过的将邻居节点入队
                seach_queue.push(node)

bfs(GRAPH, 'A')
print('=' * 40)
dfs(GRAPH, 'A')
print('=' * 40)
dfs1(GRAPH, 'A')
